#include <fstream>
#include <cstring>
#include "headfiles.h"

using namespace std;

bool addNode(ListNode * &head, int val) {
	ListNode *n = (ListNode *)malloc(sizeof(ListNode));
	if (n == NULL) {
		cout << "Allocate node buffer error!" << endl;
		return false;
	}

	n->val = val;
	n->next = head;
	head = n;

	return true;
}

bool removeNode(ListNode * &head, int val) {
	ListNode *n;
	if (head->val == val) {
		n = head;
		head = head->next;
		free(n);
		return true;
	}

	ListNode *n_pre = head;
	n = n_pre->next;
	while (n) {
		if (n->val == val) {
			break;
		}
		n_pre = n;
		n = n->next;
	}

	if (n == NULL) {
		cout << "node does not exist!" << endl;
		return false;
	}
	else {
		n_pre->next = n->next;
		free(n);
		return true;
	}

	return true;
}

ListNode *createLinkList(char *file_name) {
	if (file_name == NULL) {
		return NULL;
	}

	fstream fs;
	fs.open(file_name, fstream::in);
	if (!fs.is_open()) {
		cout << "File " << file_name << " open error!" << endl;
		return NULL;
	}
	
	string str;
	ListNode *head = NULL;
	while (fs >> str) {
		if (str.empty()) {
			return head;
		}

		int val = atoi(str.c_str());
		if (!addNode(head, val)) {
			cout << "Add node error!" << endl;
			return NULL;
		}
	}

	return head;
}

void printLinkList(ListNode *head) {
	cout << "Link list is:" << endl;
	ListNode *n = head;
	while (n) {
		cout << n->val << endl;
		n = n->next;
	}

	cout << endl;

	return;
}

void destroyLinkList(ListNode *head) {
	if (head == NULL) {
		return;
	}

	ListNode *n = head;
	ListNode *next;
	while (n) {
		next = n->next;
		free(n);
		n = next;
	}

	return;
}

// return pointer to the current node structure
ListNode * addNodeDoubleLinkList(ListNode *&head, int val) {
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	if (node == NULL) {
		cout << "Allocate node buffer error!" << endl;
		return NULL;
	}

	memset(node, 0, sizeof(ListNode));
	node->val = val;
	if (head == NULL) {
		head = node;
	}
	else {
		node->next = head;
		head->prev = node;
		head = node;
	}

	return node;
}

// n is the location of the node to be linked by the last node
ListNode *createLoopLinkList(char *file_name, unsigned int n) {
	if (file_name == NULL) {
		cout << "Input file name error, NULL!" << endl;
		return NULL;
	}

	fstream nf;
	nf.open(file_name, fstream::in);
	if (!nf.is_open()) {
		cout << "File " << file_name << " open error!" << endl;
		return NULL;
	}

	string str;
	ListNode *head = NULL;
	ListNode *last_node = NULL;
	ListNode *node;

	while (nf >> str) {
		if (str.empty()) {
			break;
		}

		int val = atoi(str.c_str());
		node = addNodeDoubleLinkList(head, val);
		if (node == NULL) {
			cout << "Add node " << val << " error!" << endl;
			return NULL;
		}
		if (last_node == NULL) {
			last_node = node;
		}
	}

	if (last_node == NULL) {
		cout << "No link list is created!" << endl;
		return NULL;
	}

	//find the nth node and link the last node to the nth node
	unsigned int count = 0;
	ListNode *cur_node;
	cur_node = head;
	while (count < n && cur_node != NULL) {
		cur_node = cur_node->next;
		++count;
	}

	if (cur_node == NULL) {
		cout << "Link list has less than " << n << " nodes." << endl;
		return NULL;
	}
	else {
		last_node->next = cur_node;
	}

	return head;
}

ListNode * findJointNode(ListNode *head) {
	if (head == NULL) {
		cout << "Empty link list!" << endl;
		return NULL;
	}

	ListNode *n1, *n2;
	n1 = n2 = head;

	while (n1 != NULL && n2 != NULL) {
		n1 = n1->next;
		n2 = n2->next;
		if (n2 == NULL) {
			cout << "Error, no loop in the link list!" << endl;
			return NULL;
		}
		n2 = n2->next;
		if (n1 == n2) {
			break;
		}
	}

	// reset n1 to head;
	n1 = head;
	while (n1 != NULL && n2 != NULL) {
		if (n1 == n2) {
			break;
		}

		n1 = n1->next;
		n2 = n2->next;
	}

	if (n1 == NULL || n2 == NULL) {
		cout << "Cannot find the node!" << endl;
		return NULL;
	}

	return n1; 
}

void releaseLoopLinkList(ListNode *head) {
	if (head == NULL) {
		return;
	}

	ListNode *joint_node = findJointNode(head);
	ListNode *node = head;
	bool second_hit = false;
	while (node) {
		if (node == joint_node) {
			if (second_hit == false) {
				second_hit = true;
			}
			// The joint node is already release, just return;
			else {
				return;
			}
		}

		ListNode *cur_node = node;
		cout << "Release node value: " << node->val << endl;
		node = node->next;
		free(cur_node);
	}

	return;
}

